package gee

type node struct {
	pattern  string
	part     string
	children []*node
	isWild   bool
}

// matchChild 找到第一个匹配成功的节点, 用于插入
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.isMatchPart(part) {
			// 匹配上
			return child
		}
	}
	return nil
}

// isMatchPart
// @Description: 是否节点匹配part
// @receiver n *node
// @param part string
// @return bool
func (n *node) isMatchPart(part string) bool {
	if n.part == part || n.isWild {
		return true
	}
	return false
}

// matchChildren 找到当前层级的所有匹配的节点, 用于查找
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)

	for _, child := range n.children {
		if child.isMatchPart(part) {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

// insert
// @Description: 插入路由
// @receiver n *node
// @param pattern string 待匹配路由
// @param parts []string 待匹配路由的分段
// @param height int	 当前需要插入时的层级
func (n *node) insert(pattern string, parts []string, height int) {
	if len(parts) == height {
		// 找到了当前层级,则赋值 pattern 并直接返回; /的parts=[] /hello的parts=["hello"]
		n.pattern = pattern
		return
	}

	// 找当前层级的某一个child
	part := parts[height]
	child := n.matchChild(part)

	if child == nil {
		// 没找到就添加
		child = &node{
			part:   part,
			isWild: part[0] == ':' || part[0] == '*',
		}
		n.children = append(n.children, child) // 将新的child加入到n节点
	}
	// 找到了就复用, 直接插下一分段
	child.insert(pattern, parts, height+1)
}

// search
// @Description: 查找某个node
// @receiver n *node
// @param parts []string
// @param height int
// @return *node
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || (n.part != "" && n.part[0] == '*') {
		if n.pattern == "" {
			// 找到对应的层级(可能精确或模糊匹配到),但是该层级不是终点
			return nil
		} else {
			return n
		}
	}

	// 找出当前层级的所有child
	part := parts[height]
	children := n.matchChildren(part)

	// 继续匹配当前层级的所有child,如果有child匹配到,则直接返回
	for _, child := range children {
		ln := child.search(parts, height+1) // 保证模糊匹配到时,能直接返回而不是继续循环
		if ln != nil {
			return ln
		}
	}
	// 如果所有的child,都没有匹配到,则返回nil
	return nil
}
